package mysgoog.MC;

import java.text.SimpleDateFormat;
import java.util.*;

import mysgoog.board.*;
import mysgoog.bot.*;
import mysgoog.gtp.*;
import mysgoog.util.Lib;
import mysgoog.bot.algo.*;

public class MCManager {
	private static final int mostdepth = 3;
	private static final float[] Valuepara = { 0, 4, (float) 3, (float) 2 };
	private static final float[] Openpara = { 0, 200, (float) 1, (float) 0.5 };
	Color[] board = new Color[Config.getBoardSize() * Config.getBoardSize()];
	int[] num = new int[Config.getBoardSize() * Config.getBoardSize()];
	float[] value = new float[Config.getBoardSize() * Config.getBoardSize()];
	Color[] tmpboard = new Color[Config.getBoardSize() * Config.getBoardSize()];;
	Color[] save = new Color[Config.getBoardSize() * Config.getBoardSize()];	
	Color color = null;
	Vector<Integer> emptyvec = null;
	Vector<Integer> basicvec = null;
	boolean[] visiting = new boolean[Config.getBoardSize()
			* Config.getBoardSize()];
	boolean[] eye = new boolean[Config.getBoardSize() * Config.getBoardSize()];
	double[] evalue = new double[Config.getBoardSize() * Config.getBoardSize()];
	int tmp[] = new int[10];
	Color newcolor = null;
	public int consttimes = 6000;
	int count;
	final int eyecount = 6;
	Board recentboard;
	boolean blackcolor;
	boolean whitecolor;
	boolean lastkill;
	int lib = 0;
	int kill;
	BasActionMgr basic;
	Vector moves;
	Evaluator eva;
	Vector<Integer> vec = new Vector<Integer>();
	double libiry = 0;
	private float[] AddValue = new float[Config.getBoardSize()
			* Config.getBoardSize()];

	public MCManager(Color color, Board recentboard) {
		this.color = color;
		for (int i = 0; i < Config.getBoardSize() * Config.getBoardSize(); i++) {
			board[i] = recentboard.getStone(i);
			// Lib.debug(board[i].toString());
		}
		this.recentboard = recentboard;
		this.moves = null;
		eva = new Evaluator((DragonBoard) recentboard);
		for (int i = 0; i < Config.getBoardSize() * Config.getBoardSize(); i++) {
			for (int j = 0; j < Config.getBoardSize() * Config.getBoardSize(); j++)
				visiting[j] = false;
			libiry = 0;
			AddValue[i] = SearchFight(0, i, color, Config.getEmptyBoard().posX(
					i), Config.getEmptyBoard().posY(i));
			AddValue[i] = (float) (libiry - Math.abs(AddValue[i]));
		}
	}

	public MCManager(Color color, Board recentboard, Vector moves) {
		this.color = color;
		for (int i = 0; i < Config.getBoardSize() * Config.getBoardSize(); i++) {
			board[i] = recentboard.getStone(i);
			// Lib.debug(board[i].toString());
		}
		this.recentboard = recentboard;
		this.moves = moves;
		eva = new Evaluator((DragonBoard) recentboard);
		for (int i = 0; i < Config.getBoardSize() * Config.getBoardSize(); i++) {
			for (int j = 0; j < Config.getBoardSize() * Config.getBoardSize(); j++)
				visiting[j] = false;
			libiry = 0;
			AddValue[i] = SearchFight(0, i, color, Config.getEmptyBoard().posX(
					i), Config.getEmptyBoard().posY(i));
			AddValue[i] = (float) (libiry - Math.abs(AddValue[i]));
		}
	}

	public MCManager(Color color, Board recentboard, int pos) {
		Vector<Integer> tmpvec = new Vector<Integer>();
		this.color = color;
		for (int i = 0; i < Config.getBoardSize() * Config.getBoardSize(); i++) {
			board[i] = recentboard.getStone(i);
			// Lib.debug(board[i].toString());
		}
		this.recentboard = recentboard;
		this.moves = moves;
		eva = new Evaluator((DragonBoard) recentboard);
		int x = Config.getEmptyBoard().posX(pos);
		int y = Config.getEmptyBoard().posY(pos);
		moves = new Vector<Integer>();
		for (int i = -2; i < 3; i++)
			for (int j = -2; j < 3; j++) {
				int xx = x + i;
				int yy = y + j;
				if (recentboard.isLegal(color, Config.getEmptyBoard().makePos(
						xx, yy)))
					moves.add(Config.getEmptyBoard().makePos(xx, yy));
			}
		emptyvec = legalmove();
		for (int i = 0; i < moves.size(); i++) {
			if (emptyvec.contains(moves.get(i)))
				tmpvec.add((Integer) moves.get(i));
		}
		if (tmpvec.size() == 0)
			moves = null;
		else
			moves = tmpvec;
		for (int i = 0; i < Config.getBoardSize() * Config.getBoardSize(); i++) {
			for (int j = 0; j < Config.getBoardSize() * Config.getBoardSize(); j++)
				visiting[j] = false;
			AddValue[i] = SearchLib(0, i, Config.getEmptyBoard().posX(i),
					Config.getEmptyBoard().posY(i));
		}

	}

	public Vertex MCGen() {
		int selectmove;
		int best;
		long end;

		final double mineva = -100;
		// Lib.debug("Enter MCGen");
		// for (int i = 0; i < Config.getBoardSize() * Config.getBoardSize();
		// i++) {
		// if (eye[i]) Lib.debug(((Integer)i).toString());
		// }
		// if (emptyvec.size() == 0) {
		// Lib.debug("FIRST FINISH!");
		// }
		basic = new BasActionMgr(color, recentboard);
		basicvec = basic.getPlace();
		emptyvec = legalmove();
		// end = System.currentTimeMillis();
		// System.err.println("Fisrt cost:" + (end - begin) + "ms");
		// for (int i = 0; i < Config.getBoardSize() * Config.getBoardSize();
		// i++) {
		// if (eye[i])
		// Lib.debug(((Integer) i).toString());
		// }
		int evanum = 0;
		double evatotal = 0;
		double evaaver;
		for (int i = 0; i < Config.getBoardSize() * Config.getBoardSize(); i++) {
			if ((!recentboard.isLegal(color, i)) || (!emptyvec.contains(i)) || (!eva.easyEvaluate(i, color))) {
				evalue[i] = mineva;
			} else {
				// long before = System.currentTimeMillis();
				evalue[i] = eva.evaluate(i, color, -1);
				// long after = System.currentTimeMillis();
				// System.err.println("each cost:" + (after - before) + "ms");
				evanum++;
				evatotal = evatotal + evalue[i];
			}
		}
		// end = System.currentTimeMillis();
		// System.err.println("1.5 cost:" + (end - begin) + "ms");
		evaaver = evatotal / evanum;
		for (int i = 0; i < Config.getBoardSize() * Config.getBoardSize(); i++) {
			if (evalue[i] < evaaver) {
				emptyvec.removeElement(i);
			}
		}
		if (emptyvec.size() == 0) {
			// Lib.debug("FINISH!");
			return new Vertex(-1, -1);
		}
		// end = System.currentTimeMillis();
		// System.err.println("Second cost:" + (end - begin) + "ms");

		for (int i = 0; i < 10; i++)
			tmp[i] = -1;
		// Lib.debug("ENTER");
		for (int i = 0; i < basicvec.size(); i++) {
			tmp[i] = basicvec.get(i);
			if (!emptyvec.contains(tmp[i]))
				tmp[i] = -1;
			// Lib.debug(((Integer) tmp[i]).toString());
		}
		basicvec.clear();
		for (int i = 0; i < 3; i++) {
			if (tmp[i] != -1)
				basicvec.add(tmp[i]);
		}
		if (moves != null) {
			basicvec.clear();
			emptyvec.clear();
			emptyvec = moves;
		}
		tmpboard = new Color[Config.getBoardSize() * Config.getBoardSize()];
		System.arraycopy(board, 0, tmpboard, 0, Config.getBoardSize()
				* Config.getBoardSize());
		// end = System.currentTimeMillis();
		// System.err.println("Third cost:" + (end - begin) + "ms");

		long begin = System.currentTimeMillis();
		end = begin;
		while (end < begin + consttimes) {
			// Lib.debug(((Integer)emptyvec.size()).toString());
			int i = 0;
			if (basicvec.size() * 20 <= i) {
				i = Math.abs((new Random().nextInt())) % emptyvec.size();
				selectmove = emptyvec.get(i);
				num[selectmove]++;
				value[selectmove] = value[selectmove] + AddValue[selectmove];
				System.arraycopy(tmpboard, 0, board, 0, Config.getBoardSize()
						* Config.getBoardSize());
				board[selectmove] = color;
			} else {
				i = Math.abs((new Random().nextInt())) % basicvec.size();
				selectmove = basicvec.get(i);
				num[selectmove]++;
				value[selectmove] = (float) (value[selectmove] + 1.5 + AddValue[selectmove]);
				System.arraycopy(tmpboard, 0, board, 0, Config.getBoardSize()
						* Config.getBoardSize());
				board[selectmove] = color;
			}
			long before = System.currentTimeMillis();
			MCWork(selectmove, color);
			end = System.currentTimeMillis();
			// System.err.println("each cost:" + (after - before) + "ms");
		}
		// end = System.currentTimeMillis();
		// System.err.println(" cost:" + (end - begin) + "ms");

		best = -1;
		for (int i = 0; i < Config.getBoardSize() * Config.getBoardSize(); i++) {
			if ((num[i] != 0) && (recentboard.isLegal(color, i))) {
				if (best == -1) {
					best = i;
				} else if ((value[i] / num[i]) > (value[best] / num[best])) {
					best = i;
				}
				Lib.debug(((Integer) i).toString());
				Lib.debug(((Float) (value[i] / num[i])).toString());
			}
		}
		// Lib.debug("Best");
		// Lib.debug(((Integer) best).toString());
		int x = Config.getEmptyBoard().posX(best);
		int y = Config.getEmptyBoard().posY(best);
		Vertex ret = new Vertex(x, y);
		// Lib.debug(((Integer)x).toString());
		// Lib.debug(((Integer)y).toString());
		// if (tmpboard[Config.getEmptyBoard().makePos(x, y)] == (Color.EMPTY))
		// Lib.debug("NOTEMPTYNOTEMPTY");
		return ret;
	}

	private float MCWork(int selectmove, Color nowcolor) {
		// Lib.debug("Enter MCWork");
		long first = System.currentTimeMillis();
		lastkill = false;
		kill = -1;
		vec = legalmove();
		int step = 0;
		// long last = System.currentTimeMillis();
		// System.err.println("each-Fisrt cost:" + (last - first) + "ms");
		while ((vec.size() != 0) && (step <= 200)) {
			// Lib.debug(((Integer)vec.size()).toString());
			kill = -1;
			if (!lastkill) {
				for (int i = 0; i < Config.getBoardSize()
						* Config.getBoardSize(); i++)
					visiting[i] = false;
				for (int i = 0; i < Config.getBoardSize()
						* Config.getBoardSize(); i++) {
					if (!(board[i] == Color.EMPTY) && !visiting[i])
						if (kill == -1) {
							lib = 0;
							findkill(i, board[i]);
							if (lib != 1)
								kill = -1;
						}
				}
			} else
				lastkill = false;
			int move;
			if (kill == -1) {
				move = Math.abs((new Random().nextInt())) % vec.size();
				move = vec.get(move);
			} else {
				move = kill;
				lastkill = true;
			}
			if (nowcolor == Color.BLACK)
				nowcolor = Color.WHITE;
			else
				nowcolor = Color.BLACK;
			board[move] = nowcolor;
			vec = legalmove();
			step++;
		}
		// last = System.currentTimeMillis();
		// System.err.println("each-Second cost:" + (last - first) + "ms");

		checkvalue(selectmove);
		// last = System.currentTimeMillis();
		// System.err.println("each-Third cost:" + (last - first) + "ms");
		return 0;
	}

	private void checkvalue(int selectmove) {
		int ret = 0;
		for (int i = 0; i < visiting.length; i++)
			visiting[i] = false;
		for (int i = 0; i < Config.getBoardSize() * Config.getBoardSize(); i++) {
			if (board[i] == (color) && !visiting[i]) {
				ret = ret + culvalue(i, color);
			}
		}
		value[selectmove] = value[selectmove] + ret;
	}

	private int culvalue(int place, Color color) {
		// Lib.debug("culvalue");
		int ret = 1;
		int x, y;
		if ((board[place] != (color)) && (board[place] != (Color.EMPTY)))
			return 0;
		if (visiting[place])
			return 0;
		visiting[place] = true;
		x = Config.getEmptyBoard().posX(place);
		y = Config.getEmptyBoard().posY(place);
		if (x - 1 >= 0)
			ret = ret
					+ culvalue(Config.getEmptyBoard().makePos(x - 1, y), color);
		if (x + 1 < Config.getBoardSize())
			ret = ret
					+ culvalue(Config.getEmptyBoard().makePos(x + 1, y), color);
		if (y - 1 >= 0)
			ret = ret
					+ culvalue(Config.getEmptyBoard().makePos(x, y - 1), color);
		if (y + 1 < Config.getBoardSize())
			ret = ret
					+ culvalue(Config.getEmptyBoard().makePos(x, y + 1), color);
		return ret;
	}

	private Vector<Integer> legalmove() {
		Vector<Integer> vec = new Vector<Integer>();
		for (int i = 0; i < Config.getBoardSize() * Config.getBoardSize(); i++)
			visiting[i] = false;
		for (int i = 0; i < Config.getBoardSize() * Config.getBoardSize(); i++)
			if ((!visiting[i]) && (board[i] == (Color.EMPTY))) {
				int tmp = countlib(i, board[i]);
				if (tmp == 0)
					remove(i, board[i]);
			}
		for (int i = 0; i < Config.getBoardSize() * Config.getBoardSize(); i++) {
			visiting[i] = false;
			eye[i] = false;
		}
		for (int i = 0; i < Config.getBoardSize() * Config.getBoardSize(); i++) {
			if (!visiting[i]) {
				if (board[i] == (Color.EMPTY)) {
					newcolor = null;
					count = 0;
					blackcolor = false;
					whitecolor = false;
					boolean iseye = true;
					iseyes(i);
					if ((blackcolor && whitecolor)
							|| (!blackcolor && !whitecolor))
						iseye = false;
					if ((iseye) && (count < eyecount))
						seteye(i);
				}
			}
			if ((board[i] == (Color.EMPTY)) && (!eye[i]))
				vec.add(i);
		}
		return vec;
	}

	private int countlib(int place, Color color) {
		// Lib.debug("lib");
		int ret = 0;
		int x, y;
		if ((board[place] != color) && (board[place] != Color.EMPTY))
			return 0;
		if (visiting[place])
			return 0;
		visiting[place] = true;
		if (board[place] == Color.EMPTY)
			return 1;
		x = Config.getEmptyBoard().posX(place);
		y = Config.getEmptyBoard().posY(place);
		if (x - 1 >= 0)
			ret = ret
					+ countlib(Config.getEmptyBoard().makePos(x - 1, y), color);
		if (x + 1 < Config.getBoardSize())
			ret = ret
					+ countlib(Config.getEmptyBoard().makePos(x + 1, y), color);
		if (y - 1 >= 0)
			ret = ret
					+ countlib(Config.getEmptyBoard().makePos(x, y - 1), color);
		if (y + 1 < Config.getBoardSize())
			ret = ret
					+ countlib(Config.getEmptyBoard().makePos(x, y + 1), color);
		return ret;
	}

	private float SearchLib(int depth, int place, int originx, int originy) {
		float ret = 0;
		int x, y;
		if (depth > mostdepth)
			return 0;
		if (visiting[place])
			return 0;
		visiting[place] = true;
		x = Config.getEmptyBoard().posX(place);
		y = Config.getEmptyBoard().posY(place);
		if (board[place] == Color.EMPTY)
			ret = Openpara[Math.abs(x - originx) + Math.abs(y - originy)];
		if (x - 1 >= 0)
			ret = ret
					+ SearchLib(depth + 1, Config.getEmptyBoard().makePos(
							x - 1, y), originx, originy);
		if (x + 1 < Config.getBoardSize())
			ret = ret
					+ SearchLib(depth + 1, Config.getEmptyBoard().makePos(
							x + 1, y), originx, originy);
		if (y - 1 >= 0)
			ret = ret
					+ SearchLib(depth + 1, Config.getEmptyBoard().makePos(x,
							y - 1), originx, originy);
		if (y + 1 < Config.getBoardSize())
			ret = ret
					+ SearchLib(depth + 1, Config.getEmptyBoard().makePos(x,
							y + 1), originx, originy);
		return ret;
	}

	private float SearchFight(int depth, int place, Color color, int originx,
			int originy) {
		float ret = 0;
		int x, y;
		if (depth > mostdepth)
			return 0;
		if (visiting[place])
			return 0;
		visiting[place] = true;
		if (board[place] == Color.EMPTY)
			libiry = libiry + 0.5;
		x = Config.getEmptyBoard().posX(place);
		y = Config.getEmptyBoard().posY(place);
		if (board[place] == color)
			ret = Valuepara[Math.abs(x - originx) + Math.abs(y - originy)];
		if (board[place] == color.complement())
			ret = -Valuepara[Math.abs(x - originx) + Math.abs(y - originy)];

		if (x - 1 >= 0)
			ret = ret
					+ SearchFight(depth + 1, Config.getEmptyBoard().makePos(
							x - 1, y), color, originx, originy);
		if (x + 1 < Config.getBoardSize())
			ret = ret
					+ SearchFight(depth + 1, Config.getEmptyBoard().makePos(
							x + 1, y), color, originx, originy);
		if (y - 1 >= 0)
			ret = ret
					+ SearchFight(depth + 1, Config.getEmptyBoard().makePos(x,
							y - 1), color, originx, originy);
		if (y + 1 < Config.getBoardSize())
			ret = ret
					+ SearchFight(depth + 1, Config.getEmptyBoard().makePos(x,
							y + 1), color, originx, originy);
		return ret;
	}

	private void findkill(int place, Color color) {
		int x, y;
		if ((board[place] != color) && (board[place] != Color.EMPTY))
			return;
		if (visiting[place])
			return;
		visiting[place] = true;
		if (board[place] == Color.EMPTY) {
			lib++;
			kill = place;
		}
		x = Config.getEmptyBoard().posX(place);
		y = Config.getEmptyBoard().posY(place);
		if (x - 1 >= 0)
			findkill(Config.getEmptyBoard().makePos(x - 1, y), color);
		if (x + 1 < Config.getBoardSize())
			findkill(Config.getEmptyBoard().makePos(x + 1, y), color);
		if (y - 1 >= 0)
			findkill(Config.getEmptyBoard().makePos(x, y - 1), color);
		if (y + 1 < Config.getBoardSize())
			findkill(Config.getEmptyBoard().makePos(x, y + 1), color);
	}

	private void iseyes(int place) {
		int x, y;
		if (board[place] == (Color.BLACK)) {
			blackcolor = true;
			return;
		}
		if (board[place] == (Color.WHITE)) {
			whitecolor = true;
			return;
		}
		if (visiting[place])
			return;
		count++;
		visiting[place] = true;
		x = Config.getEmptyBoard().posX(place);
		y = Config.getEmptyBoard().posY(place);
		if (x - 1 >= 0)
			iseyes(Config.getEmptyBoard().makePos(x - 1, y));
		if (x + 1 < Config.getBoardSize())
			iseyes(Config.getEmptyBoard().makePos(x + 1, y));
		if (y - 1 >= 0)
			iseyes(Config.getEmptyBoard().makePos(x, y - 1));
		if (y + 1 < Config.getBoardSize())
			iseyes(Config.getEmptyBoard().makePos(x, y + 1));
		return;
	}

	private void seteye(int place) {
		int x, y;
		if (eye[place])
			return;
		if (board[place] == Color.EMPTY) {
			eye[place] = true;
		}
		if (!(board[place] == Color.EMPTY)) {
			return;
		}
		x = Config.getEmptyBoard().posX(place);
		y = Config.getEmptyBoard().posY(place);
		if (x - 1 >= 0)
			seteye(Config.getEmptyBoard().makePos(x - 1, y));
		if (x + 1 < Config.getBoardSize())
			seteye(Config.getEmptyBoard().makePos(x + 1, y));
		if (y - 1 >= 0)
			seteye(Config.getEmptyBoard().makePos(x, y - 1));
		if (y + 1 < Config.getBoardSize())
			seteye(Config.getEmptyBoard().makePos(x, y + 1));
	}

	private void remove(int place, Color color) {
		// Lib.debug("remove");
		int x, y;
		if (!(board[place] == color))
			return;
		if (board[place] == color) {
			board[place] = Color.EMPTY;
		}
		x = Config.getEmptyBoard().posX(place);
		y = Config.getEmptyBoard().posY(place);
		if (x - 1 >= 0)
			remove(Config.getEmptyBoard().makePos(x - 1, y), color);
		if (x + 1 < Config.getBoardSize())
			remove(Config.getEmptyBoard().makePos(x + 1, y), color);
		if (y - 1 >= 0)
			remove(Config.getEmptyBoard().makePos(x, y - 1), color);
		if (y + 1 < Config.getBoardSize())
			remove(Config.getEmptyBoard().makePos(x, y + 1), color);
	}
}
